package Recursion;

import java.util.ArrayList;
import java.util.List;

public class Queen8 {

  int max = 4;//最多八个皇后
  /*
  array[i]+1表示放在第几列
  i表示放在第几行
   */
  int[] array = new int[max];
  static int count = 0;//保存有多少解法
  static int judgeCount = 0;//统计有多少次judge
  public static void main(String[] args) {

    Queen8 queen8 = new Queen8();
    queen8.check(0);
    System.out.println("一共有" + count + "种解法");
    System.out.println("一共统计了" + judgeCount + "次");
  }
//  查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
  private  boolean judge(int n){
    judgeCount++;
//  1. array[i] == array[n]表示判断第n个皇后是否和前面的n-1个皇后在同一列
//  2.Math.abs(n-i) =m Math.abs(array[n] - array[1])表示判断第n个皇后是否和第i皇后是否在同一斜线
//  n = 1放置第2列1 n = 1 array[1] = 1
//  Math.abs(1-0) == Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
//  3.判断是否在同一行，没有必要,n每次都在递增
    for (int i = 0; i < n; i++) {
      if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
        return false;
      }
    }
    return true;

  }

//  打印皇后的位置
  private void print(){
    count++;
    for (int ele : array) {
      System.out.print(ele + " ");
    }
    System.out.println();

  }

//  放置皇后
//  特别注意: check 是每一次递归时，进入到check中都有 for(int i = 0; i 〈 max; i++)，因此会有回溯
  private void check(int n){
    if (n == max){//表示已经放置了8个皇后
      print();
      return;
    }
//  先把当前这个皇后n ,放到该行的第1列
    for (int i = 0; i < max; i++) {
      array[n] = i;
//  判断当放嚣第n个皇后到i列时,是否冲突
      if (judge(n)){//不冲突
//        开始递归，放下一个皇后
        check(n+1);
      }
//  如果冲突，就继续执行 array[n] = i;即将第n个皇后，放在本行的后一个位置

    }
  }
}
